package utiles;

import java.util.*;
import java.io.*;

public class Utiles {
		
	public static boolean esPar(Integer a){
		return a%2 == 0;
	}
	
	public static boolean esImpar(Integer a){
		return !esPar(a);
	}
	
	public static <E> Set<E> toSet(E[] e) {
    	Set<E> s = FactoriaDeColecciones.creaSet();
    	for(E o : e){
    		s.add(o);
    	}
    	return s;
    }
	
	public static <E> Set<E> toSetMenosElemento(E[] e, E e1) {
    	Set<E> s = FactoriaDeColecciones.creaSet();
    	for(E o : e){
    		s.add(o);
    	}
    	s.remove(e1);
    	return s;
    }
	
	
	public static <E> Set<E> toSet(Iterable<E> l) {
    	Set<E> s = FactoriaDeColecciones.creaSet();
    	for(E o : l){
    		s.add(o);
    	}
    	return s;
    }
	
	public static <E> Set<E> toSetMenosElemento(Iterable<E> l,E e) {
    	Set<E> s = FactoriaDeColecciones.creaSet();
    	for(E o : l){
    		s.add(o);
    	}
    	s.remove(e);
    	return s;
    }
	
	public static <E> List<E> toList(E[] e) {
    	List<E> s = FactoriaDeColecciones.creaList();
    	for(E o : e){
    		s.add(o);
    	}
    	return s;
	}
	
	public static <E> List<E> toList(Iterable<E> i) {
    	List<E> s = FactoriaDeColecciones.creaList();
    	for(E o : i){
    		s.add(o);
    	}
    	return s;
	}
   
	
	public static <E> SortedSet<E> toSortedSet(E[] e) {
    	SortedSet<E> s = FactoriaDeColecciones.creaSortedSet();
    	for(E o : e){
    		s.add(o);
    	}
    	return s;
    }
	
	public static <E> SortedSet<E> toSortedSet(E[] e, Comparator<? super E> cmp) {
    	SortedSet<E> s = FactoriaDeColecciones.creaSortedSet(cmp);
    	for(E o : e){
    		s.add(o);
    	}
    	return s;
    }
	
	public static <E> SortedSet<E> toSortedSet(Iterable<E> e) {
    	SortedSet<E> s = FactoriaDeColecciones.creaSortedSet();
    	for(E o : e){
    		s.add(o);
    	}
    	return s;
    }
	
	public static <E> SortedSet<E> toSortedSet(Iterable<E> e, Comparator<? super E> cmp) {
    	SortedSet<E> s = FactoriaDeColecciones.creaSortedSet(cmp);
    	for(E o : e){
    		s.add(o);
    	}
    	return s;
    }
	
	public static <E1,E2> boolean hayInterseccion(Set<E1> c1, Set<E2> c2){
		boolean r = false;
		for(E1 e : c1){
			r = r || c2.contains(e); if(r) break;
		}
		return r;
	}
	
	private static class OrdenNatural<T extends Comparable<? super T>> implements Comparator<T> {
		
		public int compare(T o1, T o2){
			return o1.compareTo(o2);
		}
	}
	
	private static class OrdenOpuestoAlNatural<T extends Comparable<?  super T>> implements Comparator<T> {
		
		public int compare(T o1, T o2){
			return o2.compareTo(o1);
		}

	}
	
	public static <T extends Comparable<? super T>> Comparator<T> getOrdenNatural(){
		return new OrdenNatural<T>();
	}

	public static <T extends Comparable<? super T>> Comparator<T> getOrdenOpuestoAlNatural(){
		return new OrdenOpuestoAlNatural<T>();
	}
	
	private static PipedOutputStream os = null;
	private static PipedInputStream is = null;
	private final static Integer bufferSize=1000000;
	
	public static Boolean existeFichero(String f){
		File file = new File(f);
		return file.exists();
	}
	
	public static <T extends Serializable> void guarda(T o, String f){
		if(existeFichero(f))
			throw new FicheroYaExistente("El fichero " + f + " ya existe");
		try{
			FileOutputStream ostream = new FileOutputStream(f);
			ObjectOutputStream p = new ObjectOutputStream(ostream);
			p.writeObject(o);
		}
		catch(Exception e){e.printStackTrace();}
	}
	
	@SuppressWarnings("unchecked")
	public static <T extends Serializable> T carga(String f){
		T o1=null;
		try{
		   FileInputStream istream = new FileInputStream(f);
		   ObjectInputStream p = new ObjectInputStream(istream);
		   o1 =(T) p.readObject();
		}
		catch(Exception e){e.printStackTrace();}
		return o1;
	}
	
	@SuppressWarnings("unchecked")
	public static <T extends Serializable> T copia(T o){
		T o1 = null;
		try{
			if(os ==null)
				os = new PipedOutputStream();
			
			if(is==null)
				is = new PipedInputStream(os,bufferSize);
			
			ObjectOutputStream p = new ObjectOutputStream(os);
			p.writeObject(o);
			
			ObjectInputStream p1 = new ObjectInputStream(is);
			o1=(T)p1.readObject();
		}
		catch(Exception e){e.printStackTrace();}
		return o1;		
	}

	
	public static <E extends Comparable<? super E>> boolean esMenor(E e1, E e2){
		return e1.compareTo(e2)< 0;
	}
	
	public static <E extends Comparable<? super E>> boolean esMenorOIgual(E e1, E e2){
		return e1.compareTo(e2)<= 0;
	}
	
	public static <E> boolean esMenor(E e1, E e2, Comparator<? super E> cmp){
		return cmp.compare(e1,e2)< 0;
	}
	
	public static <E> boolean esMenorOIgual(E e1, E e2, Comparator<? super E> cmp){
		return cmp.compare(e1,e2)<= 0;
	}
	
	public static <E extends Comparable<? super E>> boolean esMayorOIgual(E e1, E e2){
		return e1.compareTo(e2)>= 0;
	}
	
	public static <E extends Comparable<? super E>> boolean esMayor(E e1, E e2){
		return e1.compareTo(e2)> 0;
	}
	
	
	public static <E> boolean esMayorOIgual(E e1, E e2, Comparator<? super E> cmp){
		return cmp.compare(e1,e2)>= 0;
	}
	
	public static <E> boolean esMayor(E e1, E e2, Comparator<? super E> cmp){
		return cmp.compare(e1,e2) > 0;
	}
	
	public static <E extends Comparable<? super E>> E min(E e1, E e2){
		return e1.compareTo(e2)<= 0 ? e1 : e2;
	}
	
	public static <E> E min(E e1, E e2, Comparator<? super E> cmp){
		return cmp.compare(e1, e2)<= 0 ? e1 : e2;
	}
	
	public static <E extends Comparable<? super E>> E min(E e1, E e2, E e3){
		E r = Utiles.min(e1, e2);
		return Utiles.min(r,e3);
	}
	
	public static <E> E min(E e1, E e2, E e3, Comparator<? super E> cmp){
		E r = Utiles.min(e1, e2, cmp);
		return Utiles.min(r,e3,cmp);
	}
	
	public static <E extends Comparable<? super E>> E min(List<E> lista, int inf, int sup){
		E r = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.min(r, lista.get(i));
		}
		return r;
	}
	
	public static <E> E min(List<E> lista, int inf, int sup, Comparator<? super E> cmp){
		E r = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.min(r, lista.get(i),cmp);
		}
		return r;
	}

	public static <E extends Comparable<? super E>> E min(E[] lista, int inf, int sup){
		E r = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.min(r, lista[i]);
		}
		return r;
	}
	
	public static <E> E min(E[] lista, int inf, int sup, Comparator<? super E> cmp){
		E r = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.min(r, lista[i],cmp);
		}
		return r;
	}
	
	public static <E extends Comparable<? super E>> Integer posicionMin(List<E> lista, int inf, int sup){
		int r = inf;
		E vm = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			E vi = lista.get(i);
			if(Utiles.esMenor(vi,vm)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}
	
	public static <E> Integer posicionMin(List<E> lista, int inf, int sup, Comparator<? super E> cmp){
		int r = inf;
		E vm = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			E vi = lista.get(i);
			if(Utiles.esMenor(vi,vm,cmp)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}

	public static <E extends Comparable<? super E>> Integer posicionMin(E[] lista, int inf, int sup){
		int r = inf;
		E vm = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			E vi = lista[i];
			if(Utiles.esMenor(vi,vm)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}
	
	public static <E> Integer posicionMin(E[] lista, int inf, int sup, Comparator<? super E> cmp){
		int r = inf;
		E vm = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			E vi = lista[i];
			if(Utiles.esMenor(vi,vm,cmp)){
				vm = vi;
				r  = i;
			}
		}
		return r;
	}

	
	public static <E extends Comparable<? super E>> E max(E e1, E e2){
		return e1.compareTo(e2)>= 0 ? e1 : e2;
	}
	
	public static <E> E max(E e1, E e2, Comparator<? super E> cmp){
		return cmp.compare(e1, e2)>= 0 ? e1 : e2;
	}
	
	public static <E extends Comparable<? super E>> E max(E e1, E e2, E e3){
		E r = Utiles.max(e1, e2);
		return Utiles.max(r,e3);
	}
	
	public static <E> E max(E e1, E e2, E e3, Comparator<? super E> cmp){
		E r = Utiles.max(e1, e2, cmp);
		return Utiles.max(r,e3,cmp);
	}
	
	
	public static <E extends Comparable<? super E>> E max(List<E> lista, int inf, int sup){
		E r = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.max(r, lista.get(i));
		}
		return r;
	}
	
	public static <E> E max(List<E> lista, int inf, int sup, Comparator<? super E> cmp){
		E r = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.max(r, lista.get(i),cmp);
		}
		return r;
	}

	public static <E extends Comparable<? super E>> E max(E[] lista, int inf, int sup){
		E r = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.max(r, lista[i]);
		}
		return r;
	}
	
	public static <E> E max(E[] lista, int inf, int sup, Comparator<? super E> cmp){
		E r = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			r = Utiles.max(r,lista[i],cmp);
		}
		return r;
	}

	public static <E extends Comparable<? super E>> Integer posicionMax(List<E> lista, int inf, int sup){
		int r = inf;
		E vm = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			E vi = lista.get(i);
			if(Utiles.esMayor(vi,vm)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}
	
	public static <E> Integer posicionMax(List<E> lista, int inf, int sup, Comparator<? super E> cmp){
		int r = inf;
		E vm = lista.get(inf);
		for(int i= inf+1; i<=sup; i++){
			E vi = lista.get(i);
			if(Utiles.esMayor(vi,vm,cmp)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}

	public static <E extends Comparable<? super E>> Integer posicionMax(E[] lista, int inf, int sup){
		int r = inf;
		E vm = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			E vi = lista[i];
			if(Utiles.esMayor(vi,vm)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}
	
	public static <E> Integer posicionMax(E[] lista, int inf, int sup, Comparator<? super E> cmp){
		int r = inf;
		E vm = lista[inf];
		for(int i= inf+1; i<=sup; i++){
			E vi = lista[i];
			if(Utiles.esMayor(vi,vm,cmp)){
				vm=vi;
				r = i;
			}
		}
		return r;
	}

	
	public static <E> void intercambia(List<E> lista, int i, int j){
		E aux;
		aux = lista.get(i);
		lista.set(i, lista.get(j));
		lista.set(j, aux);
	}
	
    public static <E> void intercambia(E[] lista, int i, int j){
    	E aux;
		aux = lista[i];
		lista[i] = lista[j];
		lista[j] = aux;
	}
    
    public static <T> Par<Integer> reordenaMedianteBanderaHolandesa(List<T> lista, T pivote, Integer inf, Integer sup,  Comparator<? super T> comparador){
    	int r = inf;
    	int k = inf;
    	int b = sup;
    	while ( k < b ) {
    	    T elem =  lista.get(k);
    	    if (elem.equals(pivote)) {
    	 
    	    } else if (Utiles.esMenor(elem, pivote, comparador)) {
    	    	Utiles.intercambia(lista, k, r);
    	    	r++;
    	    } else {
    	    	Utiles.intercambia(lista, k, b);
    	    	b--;
    	    }
    	    k++;
    	}
    	return new ParImpl<Integer>(r, b);
    }
	
    public static <T> Par<Integer> reordenaMedianteBanderaHolandesa(T[] lista, T pivote, Integer inf, Integer sup, Comparator<? super T> comparador){
    	int a = inf;
    	int i = inf;
    	int b = sup;
    	while ( i <= b ) {
    	    T elem =  lista[i];
    	    if (elem.equals(pivote)) {
    	    	i++;
    	    } else if (Utiles.esMenor(elem, pivote, comparador)) {
    	    	Utiles.intercambia(lista, i, a);
    	    	a++;
    	    	i++;
    	    } else {
    	    	Utiles.intercambia(lista, i, b);
    	    	b--;
    	    }
    	}
    	return new ParImpl<Integer>(a, b);

    }
    
    public static <T> Integer reordenaMetAlternativo(List<T> lista, T pivote, Integer inf, Integer sup,  Comparator<? super T> cmp){
    	int i = inf;
    	int j = sup;
    	while ( i < j ) {
    		if(Utiles.esMenor(lista.get(i), pivote, cmp))
    	    	i++;
    	    if(Utiles.esMayor(lista.get(j), pivote, cmp))
    	    	j--;
    	    if(Utiles.esMayorOIgual(lista.get(i), pivote, cmp) && Utiles.esMenorOIgual(lista.get(j), pivote, cmp)){
    	    	Utiles.intercambia(lista, i, j);
    	    	i++;
    	    	j--;
    	    }  	    
    	}
    	return i;
    }
    
    public static <T> Integer reordenaMetAlternativo(T[] lista, T pivote, Integer inf, Integer sup,  Comparator<? super T> cmp){
    	int i = inf;
    	int j = sup;
    	while ( i < j ) {
    	    if(Utiles.esMenor(lista[i], pivote, cmp))
    	    	i++;
    	    if(Utiles.esMayor(lista[j], pivote, cmp))
    	    	j--;
    	    if(Utiles.esMayorOIgual(lista[i], pivote, cmp) && Utiles.esMenorOIgual(lista[j], pivote, cmp)){
    	    	Utiles.intercambia(lista, i, j);
    	    	i++;
    	    	j--;
    	    }  	    
    	}
    	return i;
    }
    
    @SuppressWarnings("unchecked")
	public static <T> T mediana3(T a, T b, T c, Comparator<? super T> cmp) {
        Object[] d = {a,b,c};
        T[] d1 = (T[])d;
        int p =  Utiles.posicionMin(d1,0,2,cmp);
        if(p!=0) Utiles.intercambia(d1, 0, p);
        p =  Utiles.posicionMin(d1,1,2,cmp);
        if(p!=1) Utiles.intercambia(d1, 1, p); 
        return d1[1];
    }
      
   
	@SuppressWarnings("unchecked")
	public static <T> T mediana3(T[] de, int i, Comparator<? super T> cmp) {
		Object[] d = {de[i],de[i+1],de[i+2]};
		T[] d1 = (T[])d;
        int p =  Utiles.posicionMin(d1,0,2,cmp);
        if(p!=0) Utiles.intercambia(d1, 0, p);
        p =  Utiles.posicionMin(d1,1,2,cmp);
        if(p!=1) Utiles.intercambia(d1, 1, p); 
        return d1[1];
    }
    
	@SuppressWarnings("unchecked")
	public static <T> T mediana3(List<T> de, int i, Comparator<? super T> cmp) {
		Object[] d = {de.get(i),de.get(i+1),de.get(i+2)};	
		T[] d1 = (T[])d;
	    int p =  Utiles.posicionMin(d1,0,2,cmp);
	    if(p!=0) Utiles.intercambia(d1, 0, p);
	    p =  Utiles.posicionMin(d1,1,2,cmp);
	    if(p!=1) Utiles.intercambia(d1, 1, p); 
	    return d1[1];
    }
	
	@SuppressWarnings("unchecked")
	public static <T> T mediana5(T a, T b, T c, T d, T e, Comparator<? super T> cmp) {
        Object[] dt = {a,b,c,d,e};
        T[] d1 = (T[]) dt;
        Utiles.ordenaMedianteSeleccion(d1, 0,d1.length-1, cmp);
        return d1[3];
    }
      
   
	@SuppressWarnings("unchecked")
	public static <T> T mediana5(T[] de, int i, Comparator<? super T> cmp) {
		Object[] d = {de[i],de[i+1],de[i+2], de[i+3], de[i+4]};
		T[] d1 = (T[]) d;
        Utiles.ordenaMedianteSeleccion(d1, 0,d1.length-1, cmp);
        return d1[3];	
    }
    
	@SuppressWarnings("unchecked")
	public static <T> T mediana5(List<T> de, int i, Comparator<? super T> cmp) {
		Object[] d = {de.get(i),de.get(i+1),de.get(i+2), de.get(i+3), de.get(i+4)};	
		T[] d1 = (T[])d;
		Utiles.ordenaMedianteSeleccion(d1, 0,d1.length-1, cmp);
        return d1[3];	
    }
	
    public static <T> void ordenaMedianteSeleccion(List<T> lista, Integer inf, Integer sup, Comparator<? super T> cmp) {
    	for (int i = inf; i < sup; i++) {
    	      int pm = Utiles.posicionMin(lista, i, sup,cmp);
    	      Utiles.intercambia(lista, i, pm);
    	}
    }
    
    public static <T> void ordenaMedianteSeleccion(T[] lista, Integer inf, Integer sup, Comparator<? super T> cmp) {
    	for (int i = inf; i < sup; i++) {
    	      int pm = Utiles.posicionMin(lista, i, sup,cmp);
    	      Utiles.intercambia(lista, i, pm);
    	}
    }
    
    
    private static Random rnd   = new Random();
    public static Integer getEnteroAleatorio(Integer a, Integer b){
    	if(b<=a) throw new IllegalArgumentException(); 	
    	Integer valor = a+rnd.nextInt(b-a+1);
    	return valor;
    }

}

